{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# 期末考试 OJ 编程题"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 1.两组数的差异（10分）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "** 题目内容：**\n",
    "\n",
    "给出两组相同数量的整数，求这两组整数的差异估算，即：对应数差值平方之和。\n",
    "\n",
    "第一组为 $a1, a2....an$\n",
    "\n",
    "第二组为 $b1, b2....bn$\n",
    "\n",
    "求 $(a1-b1)^2 + (a2-b2)^2 + ... + (an-bn)^2$\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "两行，每行是一组整数，用空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "一个整数。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```shell\n",
    "1 2\n",
    "\n",
    "1 2\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "`0`"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "alist = list(map(int, input().split()))\n",
    "blist = list(map(int, input().split()))\n",
    "\n",
    "total = 0\n",
    "for i in range(len(alist)):\n",
    "    total += (alist[i] - blist[i]) ** 2\n",
    "\n",
    "print(int(total))"
   ]
  },
  {
   "source": [
    "## 2.回文字符串（10分）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "**题目内容：**\n",
    "\n",
    "给定一个字符串，判断它是否是回文字符串（即类似于peep, 12321这样的对称字符串），如果是输出True，不是则输出False。\n",
    "\n",
    "判断过程中假定只考虑字母和数字字符，而且忽略字母的大小写和其它符号（如空格、标点符号等）。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，为一个字符串。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为 `True` 或 `False`。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "`love e vol;`\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "`True`"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "s = input()\n",
    "n = []\n",
    "\n",
    "for i in s:\n",
    "    if i.isalpha():  # 判断是否为字母\n",
    "        n.append(i.lower())  # 同时转换为小写\n",
    "    elif i.isdigit():  # 判断是否为数字\n",
    "        n.append(i)\n",
    "\n",
    "n_len = len(n)\n",
    "middle = n_len // 2  # 中间位置\n",
    "flag = 0  # 标志位\n",
    "\n",
    "# 首尾比较，向中间靠拢\n",
    "for i in range(middle):\n",
    "    if n[i] == n[n_len - 1 - i]:\n",
    "        flag = 1\n",
    "    else:\n",
    "        flag = 0\n",
    "        break\n",
    "        \n",
    "if flag == 1:\n",
    "    print(True)\n",
    "else:\n",
    "    print(False)"
   ]
  },
  {
   "source": [],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 3.零的组合（10分）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "**题目内容：**\n",
    "\n",
    "给定一个包含若干个整数（可能存在重复整数）的列表，判断其中是否存在三个元素 $a,b,c$，使得 $a+b+c=0$？找出所有满足条件且不重复的这样的三个数的组合。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，列表中元素以空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为不重复组合的个数，不存在这样的组合就输出0\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "`-1 0 1 2 -1`\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "`2`\n",
    "\n",
    "（注：两个组合是 $-1，-1，2$ 和 $-1，0，1$）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "# 定义一个函数，该函数能求出组合 C(n, c)，该函数返回的是索引值列表\n",
    "def combination(n, c, com=1, limit=0, per=[]):\n",
    "    for pos in range(limit, n):\n",
    "        t = per + [pos]\n",
    "        if len(set(t)) == len(t):\n",
    "            if len(t) == c:\n",
    "                yield [pos,]\n",
    "            else:\n",
    "                for result in combination(n, c, com, com*pos, per + [pos,]):\n",
    "                    yield [pos,] + result\n",
    "\n",
    "\n",
    "alist = list(map(int, input().split()))\n",
    "n = len(alist)\n",
    "c = 3\n",
    "comb_index = combination(n, c)\n",
    "comb = []\n",
    "num = 0\n",
    "\n",
    "# 先求出所有三个数的不同组合\n",
    "for index in comb_index:\n",
    "    total = 0\n",
    "    tmp = []\n",
    "    for i in index:\n",
    "        tmp.append(alist[i])\n",
    "    comb.append(sorted(tmp))\n",
    "\n",
    "# 去除重复的组合\n",
    "comb_no_repition = []\n",
    "for i in comb:\n",
    "    if not i in comb_no_repition:\n",
    "        comb_no_repition.append(i)\n",
    "\n",
    "# 统计不重复组合里和为 0 的个数\n",
    "for i in comb_no_repition:\n",
    "    if sum(i) == 0:\n",
    "        num += 1\n",
    "\n",
    "print(num)"
   ]
  },
  {
   "source": [
    "## 4.乘积的列表（10分）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "**题目内容：**\n",
    "\n",
    "给定一个包含若干个整数的列表alist，要求返回输出列表blist，blist中的元素为除与alist对应位置上的元素之外其余各元素的乘积。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，列表中的元素以空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个列表。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "`1 2 3`\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "`[6, 3, 2]`\n",
    "\n",
    "（注：原列表的1，对应输出 6 = 2 \\* 3；原列表的 2，对应输出 3 = 1 \\* 3；原列表的 3，对应输出 2 = 1 \\* 2）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "* 一开始的想法是将所有数乘起来，然后依次除以列表里的每个数，但未考虑到除数为 0 的情况"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[6, 12, 18]\n"
     ]
    }
   ],
   "source": [
    "alist = list(map(int, input().split()))\n",
    "\n",
    "product = 1\n",
    "for i in alist:\n",
    "    product *= i\n",
    "\n",
    "blist = [product] * len(alist)\n",
    "for i in range(len(alist)):\n",
    "    blist[i] //= alist[i]\n",
    "\n",
    "print(blist)"
   ]
  },
  {
   "source": [
    "* 过后老老实实按照题目要求的思路进行求解"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[6, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "def product(xlist):\n",
    "    tmp = 1\n",
    "    for i in xlist:\n",
    "        tmp *= i\n",
    "    return tmp\n",
    "\n",
    "alist = list(map(int, input().split()))\n",
    "blist = []\n",
    "for i in range(len(alist)):\n",
    "    new_list = alist[:]  # 拷贝一份\n",
    "    new_list.pop(i)  # 剔除当前的数\n",
    "    blist.append(product(new_list))  # 列表里剩下的数求积\n",
    "\n",
    "print(blist)"
   ]
  },
  {
   "source": [
    "**注意：**\n",
    "\n",
    "这里有一个经常容易犯错的点 —— 拷贝一份列表 `new_list = alist[:]`，很容易写成 `new_list = alist`。\n",
    "\n",
    "实际上后者并没有完成拷贝，只是将同一个列表加了一个*新变量名*，在后续操作中，修改 `new_list` 也会改变 `alist`。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 5.破译密码（10分）"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "**题目内容：**\n",
    "\n",
    "A国情报局抓获敌国间谍一名，从间谍身上搜出了若干密电，在严刑逼供之下，间谍说出了密电加密方法：将明文电报（仅由大写字母构成）中的所有字母均替换为字母表中向后看的第n个字母，如果超过 Z，则从 A 继续数，这样就得到了密文，比如 ATTACK ，向后看第 2 个字母，就加密为 CVVCFM。\n",
    "\n",
    "可还没等到间谍说出加密用的密钥（数字 n），就被卧底开枪打死，间谍临死前在地板上画了 BYE 三个字母。\n",
    "\n",
    "情报局长看着一条条密电发了愁，但机智的你已经发现，原来间谍在告诉我们，所有密电的明文都以 BYE 结尾！\n",
    "\n",
    "请编写程序破译这些密电吧！\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行字符串，全部由大写字母构成的密文。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行字符串，破译后的明文。\n",
    "\n",
    "---\n",
    "\n",
    "输入样例1：\n",
    "\n",
    "`JNTQZCZF`\n",
    "\n",
    "输出样例1：\n",
    "\n",
    "`IMSPYBYE`"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "* 以下做法在考试的 Python 3.4 版本的解释器里会报错，但在本机上运行测试正常"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "IMSPYBYE\n"
     ]
    }
   ],
   "source": [
    "encode = list(input())\n",
    "n = ord(encode[-1]) - ord('E')  # 首先判断出 n 是多少\n",
    "decode = []\n",
    "\n",
    "for i in encode:\n",
    "    m = (ord(i) - n - ord('A')) % 25 + ord('A')  # 根据 n 求出对应的解密字母\n",
    "    decode.append(chr(m))\n",
    "print(''.join(decode))"
   ]
  },
  {
   "source": [
    "* 反复修改无法通过测试，因此更改思路 \n",
    "\n",
    "放弃用原来的 ASCII 码进行转换，直接列出 26 个字母，利用索引值进行操作"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "IMSPYBYE"
     ]
    }
   ],
   "source": [
    "encode = input()\n",
    "string = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "\n",
    "# 直接求出密钥 n\n",
    "n = string.index(encode[-1]) - string.index('E')\n",
    "# 解密计算明文\n",
    "for i in encode:\n",
    "    print(string[(string.index(i) - n) % 26], end='')"
   ]
  }
 ]
}